Queues are commonly used in past and current data processing systems. Some queues have been managed by hardware logic circuitry and other queues have been managed by programmed or microprogrammed routines. A large number of queues are commonly used by system control programs to control the reusable hardware and software resources of a data processing system, including queues which are themselves system resources.
Each queue is generally comprised of a plurality of entries (often called "elements") in which each element is a unit of the queue. For example, a queue may be used in a system to keep track of all I/O devices currently in the process of reading or writing a record, and at any given time the queue may have anywhere from no elements (indicating no I/O device is in use) to a large number of elements (indicating a large number of I/O devices are in use). Another example is a queue used to receive all user requests for the use of a supervisory dispatcher program (which is a system resource that allocates CPUs to user program tasks ready to be executed).
Queues may be classified into two general types according to the relative locations of the elements in the queue; and they are: (1) contiguous queues with elements physically located next to each other, and (2) chained queues with elements that can be physically dispersed anywhere in main storage (MS). An example of a contiguous queue is shown in an article entitled "First-In/First-Out Queueing Technique Using Compare and Swap" by M. Taradalsky on page 1547 of Vol. 18, No. 5, October 1975, in the IBM Technical Disclosure Bulletin.
The subject invention does not deal with contiguous queues, but deals only with chained queues and more particularly, only with single threaded chained queues having an anchor. Each chained queue has an anchor block at a predetermined location in main storage for controlling the queue. The anchor block contains an address (called an anchor pointer) which addresses the chain of elements comprising the queue, in which each element contains a pointer to a next element in the queue. The last element in the queue chain has an indicator code (often all zeroes) in its pointer location to identify it as the last element. If there is no element currently in the queue (i.e. the queue is empty), the anchor pointer contains an empty code (e.g. all zeroes) in the location of the anchor pointer.
Elements are inserted into, or deleted from, the queue by altering its anchor block. The easiest and fastest insertion and deletion is done by changing the anchor pointer itself, wherein insertion involves changing the anchor pointer to the address of a new element being put into the queue, and deletion involves changing the anchor pointer to the pointer in the element addressed by the anchor pointer. The first element in the queue (addressed directly by the anchor pointer) may be called the anchor-pointed element. A last-in/first-out (LIFO) queue operation inserts and deletes the anchor pointed element in a queue. The anchor pointed element is the newest and last element in a LIFO queue, and it is the candidate element for being dequeued.
However many data processing activities cannot use a LIFO queue operation and require some other type of dequeueing selection, such as first-in/first-out (FIFO) selection, or some other type of non-LIFO dequeueing selection.
The subject invention is primarily directed to chained queue operations requiring other than pure LIFO dequeueing selection, even though this invention may be used for LIFO dequeueing selection in combination with non-LIFO dequeueing selection.
Multiprocessing (in which two or more processors, e.g. CPUs, can simultaneously and asynchronously be executing separate instruction streams in relation to a shared MS) has been recognized in the prior art to present special problems for changing a queue in MS shared by the two or more processors. For example, it has been recognized that it is undesirable for a second processor to attempt to insert or delete an element in a queue before a first processor has completed the insertion or deletion of another element in the queue, wherein no processor should take action based on incompleted changes in the queue by another processor which would adversely affect the integrity of the queue or information obtained therefrom.
This MP problem has been generally solved in two different ways in the prior art. The first prior solution puts a lock on the queue which serializes all of its programs using the queue, so that only one program can access the queue at any given time. Such locking operation is supported by the S/370 Test and Set (TS) or Compare and Swap (CS or CDS) instruction operation on a queue lock field to prevent MP interference in accessing the lock field for selecting a program for using the queue. Programming convention among all programs using the queue requires all programs to voluntarily test the lock field and honor its state before attempting to change the queue, and only one program is selected to set on the lock field and then to change the queue. When the selected program is done changing the queue for a FIFO or non-FIFO operation, it changes the lock field to indicate an unlocked state so that another program can then set the lock on and use the queue. With this technique, only a single insertion operation or a single deletion operation can be done at a time, and simultaneous operations on the queue are not possible.
A prior shared/exclusive locking method for MP is disclosed in an article entitled "Shared Locking Without A Lock" by M. Taradalsky on page 1545 of Vol. 18, No. 5, October 1975 of the IBM Technical Disclosure Bulletin. However, the lock associated with the subject invention is not concerned with shared locking.
The second prior solution does not use any lock on the queue and applies only to queues always used as LIFO queues. A LIFO queue enables parallel requests from different programs on plural CPUs to enqueue and dequeue anchor pointed elements on a single queue, while maintaining the integrity of the queue which is of foremost importance. The second solution uses the IBM System/370 CS or CDS instruction directly on the queue anchor pointer to accomplish the element insertion or deletion of the anchor-pointed element. Background on this second solution's use of the Compare and Swap instruction on a queue element is found in the IBM System/370 Principles of Operation (GA22-7000-8) pages 7-12 to 7-14 and its Appendix A pages A40 to A46, in particular the section entitled "Free-Pool Manipulation". The Compare and Swap instruction is provided in two forms for handling either a single word field (CS instruction) or a double word field (CDS instruction); and the size of queue anchor field(s) (i.e. one word or two words) determines the use of CS or CDS for a single element insertion or deletion operation on a queue. During the CS or CDS instruction execution, no processor in a MP can interfere with a enqueueing or dequeueing operation being done by another processor, provided the field(s) being handled have the size limitation of the respective instruction, and provided that the instruction is used properly.
All queue management programs have available the main storage address of the queue anchor pointer as a displacement D2 from the current content of a specified base general register B2. Each queue management routine must then set up the operands for the CS or CDS instruction, which include loading any available general register R1 with the contents of the storage location identified by the effective address of D2(B2), which is the current anchor pointer content that addresses the first queue element. A LIFO insertion routine must initially set up the new element which later is to be inserted in the queue, store the anchor pointer in it as the element's pointer, and store the address of the element into a general register R3. A LIFO deletion routine must initially store into a general register R3 the content of the pointer within the anchor pointed element to be deleted from the queue. Then the Compare and Swap instruction CS is executed in an attempt to effect the requested insertion or deletion. When executed, the CS instruction tests R1 to determine if the content of the anchor pointer has changed: and if not, the address in R3 is stored into the anchor pointer to cause the insertion or deletion of the anchor pointer element to take place in the queue. If CS or CDS execution finds the anchor pointer has changed since R1 was set up, the insertion or deletion attempt fails, but R1 is reloaded with the current anchor pointer. A condition code (CC) for the CS instruction indicates if its execution succeeded or failed.
Experience has taught that great risk exists for destroying the queue during enqueueing and dequeueing operations when only the anchor pointer is swapped by a CS instruction for an insertion or deletion element in LIFO operations.
The integrity risk is that: (1) while a first program is attempting to dequeue a single element then on the queue after finding the pointer is zero in the anchor-pointed element; (2) a second program dequeues that element, inserts a new element, and then reinserts the element it had previously dequeued as a new anchor-pointed element; (3) all before the first program executes its CS instruction. In this case, the first program then executes its CS instruction successfully, because it will compare equally with the reinserted anchor-pointer. Unfortunately in this case, the CS instruction of the first program will insert an all zero field in the anchor-pointer to indicate an empty queue, because the first program is unaware that another element had been put into the queue in the interim period. That zero anchor pointer destroys the queue because it breaks the pointer chain and thereby ignores the existence of an element on the queue, which is then not empty.
A high risk queue is a useless queue in a high speed data processing system, because queue failure will most likely cause the data processing operation to stop or to produce erroneous results. The detection of this type of software failure may be difficult to find and correct, resulting in expensive down time for the system.
This significant risk to queue integrity has been found in the prior art to be relieved by the addition of a counter field which is in the anchor located contigously with the anchor-pointer, in which each is a one word field and they are swapped as a unit by a CDS instruction.
The CS or CDS instruction is followed by a conditional branch instruction which tests the condition code of the executed CS or CDS instruction to determine if the requested element insertion or deletion was successful. If unsuccessful, the routine loops back to again revalidate the R3 content and then re-execute the CS or CDS instruction, and if necessary repeat the looping back until the CS or CDS execution is successful.
The following prior art System/370 assembler language coding taken from the IBM System/370 Principles of Operation provides examples of insertion and deletion queue management routines which include a count value with the anchor pointer, wherein the use of the count value is essential to the integrity of the queue. The CDS instruction allows a word size anchor pointer and a contiguous word size count value to be stored into the queue anchor block as a unit on a successful execution of the CDS instruction.
______________________________________ Element Insertion Routine Initial Conditions: ______________________________________ GR0 will be loaded with the anchor pointer. GR1 will be loaded with the counter value. GR2 contains the address of the element to be added. GR3 will contain the decremented counter value. GR4 contains the address of the anchor pointer. ADDQ LM 0,1,0(4) GR0,GR1 = contents of the anchor pointer and counter. TRYAGN ST 0,0,(2) Point the new element to the current top element in the list. LR 3,1 Move the counter to GR3. BCTR 3,0 Decrement the counter. CDS 0,2,0(4) Update the anchor pointer and counter. BNE TRYAGN ______________________________________
______________________________________ Element Deletion Routine Initial Conditions: ______________________________________ GR4 contains the address of the anchor pointer. GR0 will contain the address of the anchor pointed element to be deleted. GR1 will contain the unchanged counter value. GR2 will be loaded with the anchor pointer. GR3 will be loaded with the changed counter value. DELETQ LM 2,3,0,(4) GR2,GR3 = contents of the anchor pointer and counter. TRYAGN LTR 2,2 Is the list empty? BZ EMPTY Yes, get help. L 0,0(2) No, GR0 = the pointer from the last entered element (N). LR 1,3 Move the counter to GR1. CDS 2,0,0(4) Update the anchor pointer and counter. BNE TRYAGN USE (Any Instruction) The address of the removed element is in GR2 = R1. ______________________________________
A CPU is considered to be in the process of inserting or deleting an element on a queue from the time it begins executing an element insertion or deletion routine until each routine finds the condition code of its CS or CDS instruction to be zero, indicating its insertion or deletion was successful. Thus, several programs on different CPUs in a MP can be simultaneously executing insertion or deletion programs on the same LIFO queue with contention causing looping in some of the routines until the contention ends for each routine when its CS or CDS instruction is executed successfully.
An example of interference can be visualized by having two CPUs concurrently executing queue management routines on the same LIFO queue. Either CPU may be attempting insertion or deletion on the LIFO queue asynchronous in that neither CPU knows that the other is attempting to access the LIFO queue, i.e. there is no synchronizing communication signaling between them. Suppose the first CPU routine has begun execution by setting up its operands, but has not yet executed its CDS instruction when the second CPU routine has successfully executed its CDS instruction to obtain a successful insertion or deletion of the current anchor pointed element, which changes the content of the anchor pointer at storage location D2(B2). Then when the first CPU routine executes its CDS instruction, it will be unsuccessful because the actual anchor pointer at D2(B2) or the counter, will compare unequal with the previously loaded anchor pointer in R1 or the counter in R1+1. However, the unsuccessful CDS execution will reload R1 with the new actual pointer value in preparation for the next CDS execution attempt by the first CPU. If the actual pointer value and counter at D2(B2) has not changed from the R1 and R1+ 1 content at the time of the next CDS execution, it will then be successful. Accordingly, the CDS instruction operation prevents an improper queue changed by requiring all essential conditions in order to maintain the integrity of the LIFO queue under interference situations. Prior art queue management programs have been doing these insertion and deletion routines for many years for LIFO queue operation without any lock on the queue, because this type of programming has permitted parallel LIFO insertion and deletion operations by plural programs and CPUs. Unfortunately, this type of unlocked queue operation cannot be used for non-LIFO queue operation, such as FIFO (first-in, first-out) operations.
In the prior art, certain FIFO operations have been done by using two queues which duplicate the same elements, in which one queue (i.e. input queue) is used for inserting elements and the other queue (i.e. output queue) is used for deleting elements. This technique has been used in the IEAVEDS0 and IEAVESC1 modules in a prior IBM MVS program. Elements can be inserted efficiently on the input queue by plural CPUs without queue integrity loss without then locking the input queue by using the above described compare and swap techniques for inserting each new anchor pointed element in the first queue, as explained above for LIFO element insertion. When certain conditions occur (e.g. maximum input queue size is reached or the output queue is empty), both queues are locked, further use of both queues is prevented and all elements of the first queue are removed, reordered into a FIFO sequence (e.g. by reversing its pointer chain), and then inserted into the second queue (i.e. the output queue) which is located in main storage by a second queue anchor. Output from the first queue and input to the second queue are locked during this queue reorganization process. The output queue thereafter maintains an insertion lock to prevent insertion but allows FIFO dequeuing (deletion) without a dequeueing lock by dequeuing the anchor pointed element. Hence, no new element can be inserted into the second queue while it is being emptied. The only elements that may be inserted into the second queue are those provided from the first queue under lock control.